<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <pre>
    你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

    在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

    给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
 
    示例 1:

    输入: 2, [[1,0]]
    输出: true
    解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
    示例 2:

    输入: 2, [[1,0],[0,1]]
    输出: false
    解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
     

    提示：

    输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
    你可以假定输入的先决条件中没有重复的边。
    来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/course-schedule
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    </pre>
    <script>
        let canFinish = function (numCourses, prerequisites) {
            // 如果没有先决条件，即所有的课程均没有依赖关系
            // 直接返回 true
            if (prerequisites.length === 0) {
                return true
            }

            // 维护入度表
            let inDegree = new Array(numCourses).fill(0)
            console.log('inDegree', inDegree)
            // 维护临接表
            let adj = new Map()

            for (let e of prerequisites) {
                inDegree[e[0]]++
                if (!adj.has(e[1])) adj.set(e[1], [])
                let vEdge = adj.get(e[1])
                vEdge.push(e[0])
            }
            console.log('inDegree', inDegree)
            let queue = []
            // 首先加入入度为 0 的结点
            for (let i = 0; i < numCourses; i++) { if (inDegree[i] === 0) { queue.push(i) } } while (queue.length > 0) {
                // 从队首移除
                var v = queue.shift()
                // 出队一门课程
                numCourses--
                if (!adj.has(v)) continue
                // 遍历当前出队结点的所有临接结点
                for (let w of adj.get(v)) {
                    inDegree[w]--
                    if (inDegree[w] === 0) {
                        queue.push(w)
                    }
                }
            }
            return numCourses === 0
        }
    </script>
</body>

</html>